Given a simple graph G with n vertices and m edges, the spanning tree problem\nis to find a spanning tree for a given graph G. This problem has many\napplications, such as electric power systems, computer network design and\ncircuit analysis. For a simple graph, the spanning tree problem can be solved\nin Olog n time with On m processors on the CRCW PRAM. In general,\nit is known that more efficient parallel algorithms can be developed by\nrestricting classes of graphs. In this paper, we shall propose a parallel algorithm\nwhich runs Olog n time with On log n processors on the EREW\nPRAM for constructing on proper circle trapezoid graphs.
Loading....